{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Length-3 Palindromic Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPalindromicSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度为 3 的不同回文子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，返回 <code>s</code> 中 <strong>长度为 3 </strong>的<strong>不同回文子序列</strong> 的个数。</p>\n",
    "\n",
    "<p>即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。</p>\n",
    "\n",
    "<p><strong>回文</strong> 是正着读和反着读一样的字符串。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"ace\"</code> 是 <code>\"<strong><em>a</em></strong>b<strong><em>c</em></strong>d<strong><em>e</em></strong>\"</code> 的一个子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aabca\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>长度为 3 的 3 个回文子序列分别是：\n",
    "- \"aba\" (\"<strong><em>a</em></strong>a<strong><em>b</em></strong>c<strong><em>a</em></strong>\" 的子序列)\n",
    "- \"aaa\" (\"<strong><em>aa</em></strong>bc<strong><em>a</em></strong>\" 的子序列)\n",
    "- \"aca\" (\"<strong><em>a</em></strong>ab<strong><em>ca</em></strong>\" 的子序列)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"adc\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\"adc\" 不存在长度为 3 的回文子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"bbcbaba\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>长度为 3 的 4 个回文子序列分别是：\n",
    "- \"bbb\" (\"<strong><em>bb</em></strong>c<strong><em>b</em></strong>aba\" 的子序列)\n",
    "- \"bcb\" (\"<strong><em>b</em></strong>b<strong><em>cb</em></strong>aba\" 的子序列)\n",
    "- \"bab\" (\"<strong><em>b</em></strong>bcb<strong><em>ab</em></strong>a\" 的子序列)\n",
    "- \"aba\" (\"bbcb<strong><em>aba</em></strong>\" 的子序列)\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-length-3-palindromic-subsequences](https://leetcode.cn/problems/unique-length-3-palindromic-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-length-3-palindromic-subsequences](https://leetcode.cn/problems/unique-length-3-palindromic-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabca\"', '\"adc\"', '\"bbcbaba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for c in set(s): #看实例1\n",
    "            left = s.index(c)\n",
    "            right = s.rindex(c)\n",
    "            ans += len(set(s[left+1:right])) #相同的子序列只计算一次\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 枚举两侧字符\n",
    "        for i in range(26):\n",
    "            l, r = 0, n - 1\n",
    "            # 寻找该字符第一次出现的下标\n",
    "            while l < n and ord(s[l]) - ord('a') != i:\n",
    "                l += 1\n",
    "            # 寻找该字符最后一次出现的下标\n",
    "            while r >= 0 and ord(s[r]) - ord('a') != i:\n",
    "                r -= 1\n",
    "            if r - l < 2:\n",
    "                # 该字符未出现，或两下标中间的子串不存在\n",
    "                continue\n",
    "            # 利用哈希集合统计 s[l+1..r-1] 子串的字符总数，并更新答案\n",
    "            charset = set()\n",
    "            for k in range(l + 1, r):\n",
    "                charset.add(s[k])\n",
    "            res += len(charset)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        dic = {}\n",
    "        res=set()\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            ch = s[i]\n",
    "            if ch not in dic:\n",
    "                dic[ch] = i\n",
    "                continue \n",
    "\n",
    "            pre = dic[ch]\n",
    "            for j in range(pre+1,i):\n",
    "                res.add(ch+s[j]+ch)\n",
    "            dic[ch]=i \n",
    "\n",
    "        from collections import Counter \n",
    "        c = dict(Counter(s))\n",
    "        for k,v in c.items():\n",
    "            if v >=3:\n",
    "                res.add(k*3)\n",
    "\n",
    "        return len(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        d = {}\n",
    "        st = set()\n",
    "        for c in s:\n",
    "            if c in d:\n",
    "                for cc in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    if cc in d[c]:\n",
    "                        st.add(c + cc + c)\n",
    "            for c0 in d:\n",
    "                d[c0].add(c)\n",
    "            if c not in d:\n",
    "                d[c] = set()\n",
    "        return len(st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        result = 0\n",
    "        for i in range(26):\n",
    "            # find the first and the last position of a character\n",
    "            left, right = 0, len(s) - 1\n",
    "            while(left < len(s) and ord(s[left]) != ord('a') + i):\n",
    "                left += 1\n",
    "            while(right >= 0 and ord(s[right]) != ord('a') + i):\n",
    "                right -= 1\n",
    "            # case when don't have left and right with interval bigger than 1\n",
    "            if right - left < 2:\n",
    "                continue\n",
    "            alpha = set()\n",
    "            print(f\"{left} {right}\")\n",
    "            for c in s[left + 1: right]:\n",
    "                if c not in alpha:\n",
    "                    print(c)\n",
    "                    result += 1\n",
    "                    alpha.add(c)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        from collections import Counter\n",
    "        has = []\n",
    "        ans = 0\n",
    "        for x in s:\n",
    "            if x in has:\n",
    "                continue\n",
    "            has.append(x)\n",
    "            first = s.find(x)\n",
    "            last = s.rfind(x)\n",
    "            if last-first < 2:\n",
    "                continue\n",
    "            str1 = s[first+1:last]\n",
    "            list1 = list(str1)\n",
    "            dict1 = Counter(list1)\n",
    "            ans += len(dict1)\n",
    "            #print(x ,ans)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        res_map = {}\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if s[i] not in res_map:\n",
    "                res_map[s[i]] = 0\n",
    "                start = i\n",
    "                end = i\n",
    "                temp = []\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j]==s[i]:\n",
    "                        end = j\n",
    "                    temp.append(s[j])\n",
    "                if start < end:\n",
    "                    res_map[s[i]] = len(set(temp[:end-start-1]))\n",
    "                    count += res_map[s[i]]\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        res=0\n",
    "        vis1={}\n",
    "        s=list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in vis1:\n",
    "                vis1[s[i]]=i\n",
    "                l,r=i,i\n",
    "                for pos in range(len(s)-1,-1,-1):\n",
    "                    if s[pos]==s[i]:\n",
    "                        r=pos\n",
    "                        break\n",
    "                if l!=r:\n",
    "                    vis2=Counter(s[l+1:r])\n",
    "                    # print(len(vis2))\n",
    "                    res+=len(vis2)\n",
    "                # print(vis2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "        cnts=Counter(s)\n",
    "        # print(cnts)\n",
    "        count=0\n",
    "        # for cn in cnts:\n",
    "        #     if cnts[cn]>1:\n",
    "        #         # 如果2个字符相同且挨着，视为一个字符\n",
    "        #         # \n",
    "        \n",
    "        lista=[]\n",
    "        \n",
    "        for ss in s:\n",
    "            lista.append(ss)\n",
    "        length=len(lista)\n",
    "        \n",
    "        newlista=lista.copy()\n",
    "        newlista.reverse()\n",
    "        # print(lista)\n",
    "        # print(newlista)\n",
    "        for cn in cnts:\n",
    "            if cnts[cn]>1:\n",
    "                start=lista.index(cn)\n",
    "                end=length-1-newlista.index(cn)\n",
    "                sub=set(lista[start+1:end])\n",
    "                # print(sub)\n",
    "                count+=len(sub)\n",
    "                \n",
    "                \n",
    "        return count\n",
    "      \n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        nums = []\n",
    "        dic = {}\n",
    "        for i,ss in enumerate(s):\n",
    "            if i == 0:\n",
    "                nums.append(1)\n",
    "            elif ss not in dic:\n",
    "                nums.append(nums[-1]+1)\n",
    "            else:\n",
    "                nums.append(nums[-1])\n",
    "            dic[ss] = dic.get(ss,[inf,-inf])\n",
    "            dic[ss][0] = min(dic[ss][0],i)\n",
    "            dic[ss][1] = max(dic[ss][1],i)\n",
    "        nums.append(0)\n",
    "        ret = 0 \n",
    "        for ss in s:\n",
    "            if ss not in dic:\n",
    "                continue \n",
    "            i,j = dic[ss]\n",
    "            k = len(set(list(s[i+1:j])))\n",
    "            ret += k \n",
    "            dic.pop(ss)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        first = defaultdict(int)\n",
    "        last = defaultdict(int)\n",
    "        n = len(s)\n",
    "        for i, c in enumerate(s):\n",
    "            if c in first:\n",
    "                last[c] = i\n",
    "            else:\n",
    "                first[c] = i\n",
    "        res = 0\n",
    "        for i in range(97, 123):\n",
    "            c = chr(i)\n",
    "            if c not in first or c not in last:\n",
    "                continue\n",
    "            tl, tr = first[c], last[c]\n",
    "            temp = set(list(s[tl+1:tr]))\n",
    "            res += len(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        # enumerate over the 26 chars\n",
    "        for char_ord in range(26):\n",
    "            target_char = chr(ord('a') + char_ord)\n",
    "\n",
    "            # find the first and last occurence of target char\n",
    "            lo, hi = 0, N - 1\n",
    "            while lo < hi and s[lo] != target_char:\n",
    "                lo += 1\n",
    "            while hi >= 0 and s[hi] != target_char:\n",
    "                hi -= 1\n",
    "            \n",
    "            # if there is such two same target chars, continue\n",
    "            if hi - lo < 2:\n",
    "                continue\n",
    "            \n",
    "            # if find two same target chars, calculate the distinct chars between\n",
    "            distinct_mid_chars = set([s[mid] for mid in range(lo + 1, hi)])\n",
    "            ans += len(distinct_mid_chars)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        pre = []\n",
    "        suf = []\n",
    "        n = len(s)\n",
    "        \n",
    "        start = ''\n",
    "        for i in range(n):\n",
    "            if s[i] not in start:\n",
    "                start += s[i]\n",
    "            pre.append(start)\n",
    "\n",
    "        end = ''\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if s[j] not in end:\n",
    "                end += s[j]\n",
    "            suf.append(end)\n",
    "        suf = suf[::-1]\n",
    "\n",
    "        ans = set()\n",
    "        for k in range(1, n - 1):\n",
    "            for i in range(26):\n",
    "                target_char = chr(ord('a') + i)\n",
    "                if target_char in pre[k - 1] and target_char in suf[k + 1]:\n",
    "                    # print(target_char, s[k], target_char)\n",
    "                    ans.add(target_char + s[k])\n",
    "        return len(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        ans = []\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] in ans or s[i] not in s[i+1:]:\n",
    "                continue\n",
    "            count+=len(set(s[i+1:][:-(s[i+1:][::-1].index(s[i])+1)]))\n",
    "            ans.append(s[i])\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        ans = []\n",
    "        count = 0\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] in ans or s[i] not in s[i+1:]:\n",
    "                continue\n",
    "            count+=len(set(s[i+1:][:-(s[i+1:][::-1].index(s[i])+1)]))\n",
    "            ans.append(s[i])\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "            \n",
    "        s1 = list(s)\n",
    "        s2 = list(set(s))\n",
    "        s3 = s1[::-1]\n",
    "        count = 0\n",
    "       \n",
    "        for seq in range(len(s2)):\n",
    "            n1 = s1.index(s2[seq])\n",
    "            n2 = s3.index(s2[seq])\n",
    "            if abs(n1 - (len(s1)-n2-1)) >= 2:\n",
    "                s4 = s1[n1+1:len(s1)-n2-1]\n",
    "                \n",
    "                \n",
    "                s5 = set(s4)\n",
    "                \n",
    "                    \n",
    "                count += len(s5)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\r\n",
    "        length = len(s)\r\n",
    "        pred = [0] * length\r\n",
    "        p = 1 << (ord(s[0])-97)\r\n",
    "        for i in range(1, length-1):\r\n",
    "            pred[i] = p\r\n",
    "            p |= 1 << (ord(s[i])-97)\r\n",
    "        r = set()\r\n",
    "        p = 1 << (ord(s[-1])-97)\r\n",
    "        for i in range(length-2, 0, -1):\r\n",
    "            t = pred[i] & p\r\n",
    "            for j in range(26):\r\n",
    "                if (1 << j) & t != 0:\r\n",
    "                    c = chr(97+j)\r\n",
    "                    r.add(c+s[i]+c)\r\n",
    "            p |= 1 << (ord(s[i])-97)\r\n",
    "        return len(r)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "        chars = set(s)\n",
    "        ch2idxes = {}\n",
    "        res = set()\n",
    "        for ch in chars:\n",
    "            idxes = []\n",
    "            for idx, c in enumerate(s):\n",
    "                if ch == c:\n",
    "                    idxes.append(idx)\n",
    "            ch2idxes[ch] = idxes\n",
    "\n",
    "        for idxes in ch2idxes.values():\n",
    "            if len(idxes) == 1:\n",
    "                continue\n",
    "            else:\n",
    "                if idxes[0] + 1 < idxes[-1]:\n",
    "                    k = idxes[0] + 1\n",
    "                    while k < idxes[-1]:\n",
    "                        substr = s[idxes[0]] + s[k] + s[idxes[-1]]\n",
    "                        res.add(substr)\n",
    "                        k += 1\n",
    "\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "    \"\"\"\n",
    "    执行用时：3808 ms, 在所有 Python3 提交中击败了 6.25% 的用户\n",
    "    内存消耗：19.5 MB, 在所有 Python3 提交中击败了 23.44% 的用户\n",
    "    \"\"\"\n",
    "    # def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "    #     charset = set(s)\n",
    "    #     if len(charset) == len(s):\n",
    "    #         return 0\n",
    "\n",
    "    #     char2idxes = {}\n",
    "    #     res = set()\n",
    "    #     for ch in charset:\n",
    "    #         idxes = []\n",
    "    #         for idx, c in enumerate(s):\n",
    "    #             if ch == c:\n",
    "    #                 idxes.append(idx)\n",
    "\n",
    "    #         if len(idxes) > 1 and idxes[0] + 1 < idxes[-1]:\n",
    "    #             char2idxes[ch] = idxes\n",
    "\n",
    "    #     for idxes in char2idxes.values():\n",
    "\n",
    "    #         k = idxes[0] + 1\n",
    "    #         while k < idxes[-1]:\n",
    "    #             substr = s[idxes[0]] + s[k] + s[idxes[-1]]\n",
    "    #             res.add(substr)\n",
    "    #             k += 1\n",
    "\n",
    "    #     return len(res)\n",
    "\n",
    "    \"\"\"\n",
    "    执行用时：808 ms, 在所有 Python3 提交中击败了 32.81% 的用户\n",
    "    内存消耗：19.2 MB, 在所有 Python3 提交中击败了 25.00% 的用户\n",
    "    \"\"\"\n",
    "\n",
    "    # def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "    #     charset = set(s)\n",
    "    #     if len(charset) == len(s):\n",
    "    #         return 0\n",
    "\n",
    "    #     char2idxes = {}\n",
    "    #     res = 0\n",
    "    #     for ch in charset:\n",
    "    #         idxes = []\n",
    "    #         for idx, c in enumerate(s):\n",
    "    #             if ch == c:\n",
    "    #                 idxes.append(idx)\n",
    "\n",
    "    #         if len(idxes) > 1 and idxes[0] + 1 < idxes[-1]:\n",
    "    #             char2idxes[ch] = idxes\n",
    "\n",
    "    #     for idxes in char2idxes.values():\n",
    "    #         i, j = idxes[0], idxes[-1]\n",
    "\n",
    "    #         if i + 2 == j:\n",
    "    #             res += 1\n",
    "    #         else:\n",
    "    #             res += len(set(s[i + 1: j]))\n",
    "\n",
    "    #     return res\n",
    "\n",
    "    \"\"\"\n",
    "    执行用时：252 ms, 在所有 Python3 提交中击败了 64.06% 的用户\n",
    "    内存消耗：20.2 MB, 在所有 Python3 提交中击败了 14.06% 的用户\n",
    "    \"\"\"\n",
    "    # def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "    #     charset = set(s)\n",
    "    #     if len(charset) == len(s):\n",
    "    #         return 0\n",
    "\n",
    "    #     char2idxes = {}\n",
    "\n",
    "    #     for idx, ch in enumerate(s):\n",
    "    #         if ch not in char2idxes:\n",
    "    #             char2idxes[ch] = [idx]\n",
    "    #         else:\n",
    "    #             char2idxes[ch].append(idx)\n",
    "\n",
    "    #     res = 0\n",
    "\n",
    "    #     for idxes in char2idxes.values():\n",
    "\n",
    "    #         i, j = idxes[0], idxes[-1]  # 字符 ch 在字符串 s 中的第一个位置和最后一个位置\n",
    "\n",
    "    #         if i == j or i + 1 == j:\n",
    "    #             continue\n",
    "    #         elif i + 2 == j:\n",
    "    #             res += 1\n",
    "    #         else:\n",
    "    #             res += len(set(s[i + 1: j]))\n",
    "\n",
    "    #     return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        all_set = set()\n",
    "        for _ in s:\n",
    "            all_set.add(_)\n",
    "\n",
    "        def charSub(s,c):\n",
    "            l = []\n",
    "            for _ in range(len(s)):\n",
    "                if s[_]==c:\n",
    "                    l.append(_)\n",
    "            st,e = l[0],l[-1]\n",
    "            c_set=set()\n",
    "            for _ in range(st+1,e):\n",
    "                c_set.add(s[_])\n",
    "            print(c,c_set)\n",
    "            return len(c_set)\n",
    "        return sum([charSub(s,_) for _ in all_set])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        all_set = set(s)\n",
    "\n",
    "        def charSub(s,c):\n",
    "            l = []\n",
    "            for _ in range(len(s)):\n",
    "                if s[_]==c:\n",
    "                    l.append(_)\n",
    "            st,e = l[0],l[-1]\n",
    "            c_set=set()\n",
    "            for _ in range(st+1,e):\n",
    "                c_set.add(s[_])\n",
    "            return len(c_set)\n",
    "\n",
    "        return sum([charSub(s,_) for _ in all_set])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        all_set = set(s)\n",
    "\n",
    "        def charSub(s,c):\n",
    "            l = []\n",
    "            for _ in range(len(s)):\n",
    "                if s[_]==c:\n",
    "                    l.append(_)\n",
    "            st,e = l[0],l[-1]\n",
    "            # c_set=set()\n",
    "            # for _ in range(st+1,e):\n",
    "            #     c_set.add(s[_])\n",
    "            c_set=set(s[st+1:e])\n",
    "            return len(c_set)\n",
    "\n",
    "        return sum([charSub(s,_) for _ in all_set])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "    #     chars = set(s)\n",
    "    #     ch2idxes = {}\n",
    "    #     res = set()\n",
    "    #     for ch in chars:\n",
    "    #         idxes = []\n",
    "    #         for idx, c in enumerate(s):\n",
    "    #             if ch == c:\n",
    "    #                 idxes.append(idx)\n",
    "    #         ch2idxes[ch] = idxes\n",
    "\n",
    "    #     for idxes in ch2idxes.values():\n",
    "    #         if len(idxes) == 1:\n",
    "    #             continue\n",
    "    #         else:\n",
    "    #             if idxes[0] + 1 < idxes[-1]:\n",
    "    #                 k = idxes[0] + 1\n",
    "    #                 while k < idxes[-1]:\n",
    "    #                     substr = s[idxes[0]] + s[k] + s[idxes[-1]]\n",
    "    #                     res.add(substr)\n",
    "    #                     k += 1\n",
    "\n",
    "    #     return len(res)\n",
    "\n",
    "\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "        charset = set(s)\n",
    "        if len(charset) == len(s):\n",
    "            return 0\n",
    "\n",
    "        char2idxes = {}\n",
    "        res = set()\n",
    "        for ch in charset:\n",
    "            idxes = []\n",
    "            for idx, c in enumerate(s):\n",
    "                if ch == c:\n",
    "                    idxes.append(idx)\n",
    "\n",
    "            if len(idxes) > 1 and idxes[0] + 1 < idxes[-1]:\n",
    "                char2idxes[ch] = idxes\n",
    "\n",
    "        for idxes in char2idxes.values():\n",
    "\n",
    "            k = idxes[0] + 1\n",
    "            while k < idxes[-1]:\n",
    "                substr = s[idxes[0]] + s[k] + s[idxes[-1]]\n",
    "                res.add(substr)\n",
    "                k += 1\n",
    "\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        count = 0\n",
    "        dic = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            if c not in dic:\n",
    "                dic[c] = []\n",
    "            dic[c].append(i)\n",
    "        alphas = dic.keys()\n",
    "        for k in alphas:\n",
    "            if len(dic[k]) >= 3:\n",
    "                count += 1\n",
    "                \n",
    "        for a in alphas:\n",
    "            arr_a = dic[a]\n",
    "            ia = arr_a[0]\n",
    "            for b in alphas:\n",
    "                if a == b: continue\n",
    "                arr_b = dic[b]\n",
    "                \n",
    "                l, r = 0, len(arr_b) - 1\n",
    "                \n",
    "                if arr_b[r] < ia: continue\n",
    "                while l != r:\n",
    "                    m = l + (r-l) // 2\n",
    "                    if arr_b[m] > ia:\n",
    "                        r = m\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                        \n",
    "                ib = arr_b[l]\n",
    "                l, r = 0, len(arr_a) - 1\n",
    "                if arr_a[r] < ib: continue\n",
    "                    \n",
    "                count += 1\n",
    "                \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        result = set()\n",
    "        ch2index = dict()\n",
    "        chars = set(s)\n",
    "        for c in chars:\n",
    "            indexs = []\n",
    "            for idx, c2 in enumerate(s):\n",
    "                if c == c2:\n",
    "                    indexs.append(idx)\n",
    "            if len(indexs) > 1 and indexs[0] + 1 < indexs[-1]:\n",
    "                ch2index[c] = indexs\n",
    "        #print(ch2index)\n",
    "        for key, indexs in ch2index.items():\n",
    "            mid = indexs[0] + 1\n",
    "            while mid < indexs[-1]:\n",
    "                substr = s[indexs[0]] + s[mid] + s[indexs[-1]]\n",
    "                result.add(substr)\n",
    "                mid += 1\n",
    "        print(result)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        '''anw = 0\n",
    "        for i in set(s):\n",
    "            l = s.index(i)\n",
    "            r = s.rindex(i)\n",
    "            if l < r - 1:\n",
    "                anw += len(set(s[l + 1: r]))\n",
    "        return anw'''\n",
    "        anw = 0\n",
    "        presum = [0]\n",
    "        mid = [0 for i in range(26)]\n",
    "        last = 0\n",
    "        ss= list(s)\n",
    "        for i in range(len(ss) - 1):\n",
    "            presum.append(presum[i]|(1 << (ord(ss[i]) - ord('a'))))\n",
    "        #print(presum)\n",
    "        for i in range(len(ss) - 1, -1, -1):\n",
    "            tmp = ord(ss[i]) - ord('a')\n",
    "            mid[tmp] |= presum[i] & last\n",
    "            last |= 1<<tmp\n",
    "            #print(mid)\n",
    "            #print(last)\n",
    "        for i in range(0, 26):\n",
    "            while mid[i] != 0:\n",
    "                mid[i] &= (mid[i] - 1)\n",
    "                anw += 1\n",
    "        return anw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        from bisect import bisect_left\n",
    "        dct, res = defaultdict(list), 0\n",
    "        for i in range(len(s)):\n",
    "            dct[s[i]].append(i)\n",
    "\n",
    "        for w1 in dct:\n",
    "            for w2 in dct:\n",
    "                if w1 == w2:\n",
    "                    res += 1 if len(dct[w1]) > 2 else 0\n",
    "                else:\n",
    "                    res += 1 if bisect_left(dct[w1], dct[w2][0]) != bisect_left(dct[w1], dct[w2][-1]) else 0\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_idx_in_range(self, indexes, start, end):\n",
    "        for idx in indexes:\n",
    "            if start < idx < end:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        char_index_map = defaultdict(list)\n",
    "        for idx, char in enumerate(s):\n",
    "            char_index_map[char].append(idx)\n",
    "\n",
    "        count = 0\n",
    "        for char, indexes in char_index_map.items():\n",
    "            if len(indexes) < 2:\n",
    "                continue\n",
    "            start = indexes[0]\n",
    "            end = indexes[-1]\n",
    "            for c, idxes in char_index_map.items():\n",
    "                if self.is_idx_in_range(idxes, start, end):\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "key = 'abcdefghijklmnopqrstuvwxyz'\n",
    "map_dict = dict()\n",
    "for i, c in enumerate(key):\n",
    "    map_dict[c] = 1 << i\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        suffix_list = [0] * n\n",
    "        suffix = 0\n",
    "        for i in range(n-1, 1, -1):\n",
    "            suffix |= map_dict[s[i]]\n",
    "            suffix_list[i] = suffix\n",
    "        count_dict = collections.defaultdict(int)\n",
    "        prefix = map_dict[s[0]]\n",
    "        for i in range(1, n-1):\n",
    "            c = s[i]\n",
    "            count_dict[c] |= prefix & suffix_list[i+1]\n",
    "            prefix |= map_dict[c]\n",
    "        ret = 0\n",
    "        for val in count_dict.values():\n",
    "            ret += bin(val).count('1')\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_idx_in_range(self, indexes, start, end):\n",
    "        from_i = 0\n",
    "        to_i = len(indexes) - 1\n",
    "        while from_i < to_i:\n",
    "            k = int((from_i + to_i) / 2)\n",
    "            if k == from_i or k == to_i:\n",
    "                break\n",
    "            if  start < indexes[k] < end:\n",
    "                return True\n",
    "            if indexes[k] >= end:\n",
    "                to_i = k\n",
    "            elif indexes[k] <= start:\n",
    "                from_i = k\n",
    "        return start < indexes[from_i] < end or start < indexes[to_i] < end\n",
    "    \n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        char_index_map = defaultdict(list)\n",
    "        for idx, char in enumerate(s):\n",
    "            char_index_map[char].append(idx)\n",
    "\n",
    "        count = 0\n",
    "        for char, indexes in char_index_map.items():\n",
    "            if len(indexes) < 2:\n",
    "                continue\n",
    "            start = indexes[0]\n",
    "            end = indexes[-1]\n",
    "            for c, idxes in char_index_map.items():\n",
    "                if self.is_idx_in_range(idxes, start, end):\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        res = 0\n",
    "        pos = [[] for _ in range(26)]\n",
    "        for i, c in enumerate(s):\n",
    "            pos[ord(c) - ord('a')].append(i)\n",
    "        cnt = Counter(s)\n",
    "        for i in range(26):\n",
    "            if cnt[chr(i+ord('a'))] >= 2:\n",
    "                first = pos[i][0]\n",
    "                last = pos[i][-1]\n",
    "                res += len(set(s[first+1:last]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic=defaultdict(list)\n",
    "        for i in range(len(s)): dic[s[i]].append(i)\n",
    "\n",
    "        res=0\n",
    "        for c in dic:\n",
    "            for e in dic:\n",
    "                if len(dic[e])==1: continue \n",
    "                if c==e: \n",
    "                    if len(dic[e])>=3: res+=1\n",
    "                    continue\n",
    "                l,r=0,len(dic[c])\n",
    "                while l<r:\n",
    "                    mid=(l+r)//2\n",
    "                    if dic[c][mid]<dic[e][0]: l=mid+1\n",
    "                    else: r=mid\n",
    "                if l<len(dic[c]) and dic[e][-1]>dic[c][l]: res+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        \n",
    "        ch_map = collections.defaultdict(list)\n",
    "        \n",
    "        for i, ch in enumerate(s):\n",
    "            ch_map[ch].append(i)\n",
    "            \n",
    "        count = 0\n",
    "        ch_list = list(ch_map.keys())\n",
    "        for ch in ch_list:\n",
    "            loc = ch_map[ch]\n",
    "            l = min(loc)\n",
    "            r = max(loc)\n",
    "            mid_str = s[l+1:r]\n",
    "            count += len(set(list(mid_str)))\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        charset = set(s)\n",
    "        if len(charset) == len(s):\n",
    "            return 0\n",
    "\n",
    "        char2idxes = {}\n",
    "\n",
    "        for idx, ch in enumerate(s):\n",
    "            if ch not in char2idxes:\n",
    "                char2idxes[ch] = [idx]\n",
    "            else:\n",
    "                char2idxes[ch].append(idx)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for idxes in char2idxes.values():\n",
    "\n",
    "            i, j = idxes[0], idxes[-1]  # 字符 ch 在字符串 s 中的第一个位置和最后一个位置\n",
    "\n",
    "            if i == j or i + 1 == j:\n",
    "                continue\n",
    "            elif i + 2 == j:\n",
    "                res += 1\n",
    "            else:\n",
    "                res += len(set(s[i + 1: j]))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            mp[ch].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for mid in mp:\n",
    "            v = mp[mid]\n",
    "            for left in mp:\n",
    "                cur = mp[left]\n",
    "                if len(cur) < 2:\n",
    "                    continue\n",
    "                if any(cur[0] < i < cur[-1] for i in v):\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        # length 3 palindrom is xyx or xxx\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            dic[ch].append(i)\n",
    "        res = 0\n",
    "        for k, item in dic.items():\n",
    "            v = len(item)\n",
    "            if v >= 3: # xxx\n",
    "                res += 1\n",
    "            if v >= 2: # k is the x\n",
    "                tmp = set(s[dic[k][0]+1: dic[k][-1]]) # xyx\n",
    "                tmp.discard(k)\n",
    "                res += len(tmp)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        cnt = {}\n",
    "        for i, item in enumerate(s):\n",
    "            if item not in cnt:\n",
    "                cnt[item] = [i]\n",
    "            else:\n",
    "                cnt[item].append(i)\n",
    "        ans = 0\n",
    "        for pos in cnt.values():\n",
    "            if len(pos) > 1:\n",
    "                ans += len(set(s[pos[0]+1:pos[-1]]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        table = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            table[s[i]].append(i)\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            c = chr(ord('a')+i)\n",
    "            if c in table:\n",
    "                t = 0\n",
    "                for k in range(table[c][0]+1,table[c][-1]):\n",
    "                    t = t | (1<< ord(s[k])-ord('a'))\n",
    "                ans += bin(t).count(\"1\")\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        dic=dict()\n",
    "        for i in range(len(s)):\n",
    "            a=dic.get(s[i],[])\n",
    "            a.append(i)\n",
    "            dic[s[i]]=a\n",
    "        count=0\n",
    "        def test(a,b,L):\n",
    "            left=-1\n",
    "            right=len(L)\n",
    "            while right-left>1:\n",
    "                mid=(left+right)//2\n",
    "                if L[mid]>a:\n",
    "                    right=mid\n",
    "                else:\n",
    "                    left=mid\n",
    "            if right!=len(L) and L[right]<b:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(97,123):\n",
    "            a=chr(i)\n",
    "            if len(dic.get(a,[]))<2:\n",
    "                continue\n",
    "            for j in range(97,123):\n",
    "                b=chr(j)\n",
    "                if a==b and len(dic[a])>=3:\n",
    "                    count+=1\n",
    "                elif a!=b and len(dic.get(b,[]))>=1:\n",
    "                    if test(dic[a][0],dic[a][-1],dic[b]):\n",
    "                        count+=1\n",
    "        return count\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        cnt = defaultdict(list)\n",
    "        for i, x in enumerate(s):\n",
    "            cnt[x].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for x in cnt:\n",
    "            vis = set()\n",
    "            if len(cnt[x]) > 2:\n",
    "                vis.add(x)\n",
    "            for j, pos in enumerate(cnt[x][1:]):\n",
    "                for k in range(cnt[x][j] + 1, pos):\n",
    "                    vis.add(s[k])\n",
    "            ans += len(vis)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        record = collections.defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            record[c].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for key in record:\n",
    "            if len(record[key]) > 1:\n",
    "                temp = sorted(record[key])\n",
    "                res += len(set(s[temp[0]+1:temp[-1]]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        s_dict = {}\n",
    "        j = -1\n",
    "        for i in s:\n",
    "            j += 1\n",
    "            if i in s_dict:\n",
    "                s_dict[i].append(j)\n",
    "            else:\n",
    "                s_dict[i] = [j]\n",
    "        num = 0\n",
    "        \n",
    "        for lc, ls in s_dict.items():\n",
    "            if len(ls) < 2:\n",
    "                continue\n",
    "            lb = min(ls)\n",
    "            rb = max(ls)\n",
    "            if rb - lb < 2:\n",
    "                continue\n",
    "            num += len(set(list(s[lb + 1:rb])))\n",
    "            \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        ---------\n",
    "        T - O()\n",
    "        S - O()\n",
    "        \"\"\"\n",
    "        def distinct_chars(i: int, j: int):\n",
    "            \"\"\"Calculate distinct chars in s[i:j]\"\"\"\n",
    "            tmp_set = set()\n",
    "            for k in range(i, j):\n",
    "                tmp_set.add(s[k])\n",
    "            \n",
    "            return len(tmp_set)\n",
    "\n",
    "        char_position = defaultdict(list)\n",
    "        for idx, char in enumerate(s):\n",
    "            char_position[char].append(idx)\n",
    "        \n",
    "        print(char_position)\n",
    "        res = 0\n",
    "        for char in char_position:\n",
    "            center_char = set()\n",
    "            positions = char_position[char]\n",
    "            for i in range(len(positions) - 1):\n",
    "                if positions[i + 1] - positions[i] - 1 > 0:\n",
    "                    for j in range(positions[i] + 1, positions[i + 1]):\n",
    "                        center_char.add(s[j])\n",
    "            print(f'{center_char} for {char}')\n",
    "            res += len(center_char) \n",
    "            if len(positions) >= 3:\n",
    "                res += 1     # +1 for \"{char}{char}{char}\"\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        map = [[] for _ in range(26)]\n",
    "        s_list = list(s)\n",
    "        for i, c in enumerate(s_list):\n",
    "            map[ord(c)-97].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k,v in enumerate(map):\n",
    "            if not v: continue\n",
    "            m = v[-1] - v[0] + 1\n",
    "            if m < 3: continue\n",
    "            s_sub = s_list[v[0]+1:v[-1]]\n",
    "            ans += len(list(set(s_sub)))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        '''anw = 0\n",
    "        for i in set(s):\n",
    "            l = s.index(i)\n",
    "            r = s.rindex(i)\n",
    "            if l < r - 1:\n",
    "                anw += len(set(s[l + 1: r]))\n",
    "        return anw'''\n",
    "        anw = 0\n",
    "        presum = [0]\n",
    "        mid = [0 for i in range(26)]\n",
    "        last = 0\n",
    "        ss= list(s)\n",
    "        for i in range(len(ss) - 1):\n",
    "            presum.append(presum[i]|(1 << (ord(ss[i]) - ord('a'))))\n",
    "        print(presum)\n",
    "        for i in range(len(ss) - 1, -1, -1):\n",
    "            tmp = ord(ss[i]) - ord('a')\n",
    "            mid[tmp] |= presum[i] & last\n",
    "            last |= 1<<tmp\n",
    "            #print(mid)\n",
    "            #print(last)\n",
    "        for i in range(0, 26):\n",
    "            while mid[i] != 0:\n",
    "                mid[i] &= (mid[i] - 1)\n",
    "                anw += 1\n",
    "        return anw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "方法1.枚举两端字符\n",
    "枚举26个字母第一次和最后一次出现位置，并累计两个位置之间不同字母的种数。\n",
    "\n",
    "方法2.枚举中间字符\n",
    "对于某个字符s[i]，满足的回文子系列为前缀和后缀包含的公共字符种类。\n",
    "使用一个32位整数表示前缀中每种字母是否出现，后缀同理。对于s[i]，前后缀中是否有公共字母用pre[i-1]&suf[i+1]得到\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        pre=[0]*n\n",
    "        suf=[0]*n\n",
    "        a=ord(\"a\")\n",
    "        for i in range(n):\n",
    "            pre[i]=(pre[i-1] if i else 0)|(1<<(ord(s[i])-a))\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf[i]=(suf[i+1] if i<n-1 else 0)|(1<<(ord(s[i])-a))\n",
    "        \n",
    "        #计算每个位置的字符左右两侧公共字符种类，并累计到26个字母当中\n",
    "        cnt=[0]*26\n",
    "        for i in range(1,n-1):\n",
    "            cnt[ord(s[i])-a]|=pre[i-1]&suf[i+1]\n",
    "        \n",
    "        return sum(bin(cnt[i]).count(\"1\") for i in range(26))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 前缀/后缀字符状态数组\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            # 前缀 s[0..i-1] 包含的字符种类\n",
    "            pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 后缀 s[i+1..n-1] 包含的字符种类\n",
    "            suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        # 每种中间字符的回文子序列状态数组\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]\n",
    "        # 更新答案\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 2: Prefix Sum + Bit Manipulation\n",
    "    detail: Use 32-bit integers to represent the categories in string.\n",
    "    time: O(n+|Σ|), where Σ is the character set\n",
    "    space: O(|Σ|)\n",
    "    \"\"\"\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "\n",
    "        prefix, suffix = [0] * n, [0] * n\n",
    "        for i in range(n):\n",
    "            prefix[i] = (prefix[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n-1, -1, -1):\n",
    "            suffix[i] = (suffix[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "\n",
    "        res_list = [0] * 26\n",
    "        for i in range(1, n-1):\n",
    "            res_list[ord(s[i])-ord('a')] |= prefix[i-1] & suffix[i+1]\n",
    "\n",
    "        for item in res_list:\n",
    "            res += bin(item).count(\"1\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            pre[i] = (pre[i-1] if i else 0)| (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = (suf[i+1] if i!= n-1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        \n",
    "        ans = [0] * 26\n",
    "        for i in range(1,n-1):\n",
    "            ans[ord(s[i]) - ord('a')] |= pre[i-1] & suf[i+1]\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        \n",
    "        def _bit_ones(n: int) -> int:\n",
    "            c = 0\n",
    "            while n:\n",
    "                n &= n - 1\n",
    "                c += 1\n",
    "            return c\n",
    "\n",
    "        n = len(s)\n",
    "        # pre[i]表示索引在0 ~ i-1所包含的字符种类\n",
    "        pre = [0] * (n + 1)\n",
    "        # suf[i]表示索引在i ~ n-1所包含的字符种类\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = pre[i - 1] | (1 << (ord(s[i - 1]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = suf[i + 1] | (1 << (ord(s[i]) - ord('a')))\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i]) - ord('a')] |= (pre[i] & suf[i + 1])\n",
    "        return sum(_bit_ones(t) for t in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0 for _ in range(n)]\n",
    "        suf = [0 for _ in range(n)]\n",
    "        for i in range(1, n - 1):\n",
    "            c = ord(s[i - 1]) - ord('a')\n",
    "            pre[i] = pre[i - 1] | (1 << c)\n",
    "\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            c = ord(s[i + 1]) - ord('a')\n",
    "            suf[i] = suf[i + 1] | (1 << c)\n",
    "\n",
    "        palin_mid_is = [0 for _ in range(26)]\n",
    "        for i in range(1, n - 1):\n",
    "            c = ord(s[i]) - ord('a')\n",
    "            palin_mid_is[c] |= pre[i] & suf[i]\n",
    "        return sum(palin_mid_is[c].bit_count() for c in range(26))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]\n",
    "        for c in s:\n",
    "            pre.append(pre[-1] | (1 << (ord(c) - ord('a'))))\n",
    "        suf = [0]\n",
    "        ans = set()\n",
    "        for c in s[::-1]:\n",
    "            suf.append(suf[-1] | (1 << (ord(c) - ord('a'))))\n",
    "        for i in range(1,n - 1):\n",
    "            l,r = pre[i],suf[n - 1 - i]\n",
    "            for j in range(26):\n",
    "                if l & (1 << j) and r & (1 << j):\n",
    "                    ans.add((j,ord(s[i]) - ord('a')))\n",
    "        #print(ans)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 前缀/后缀字符状态数组\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            # 前缀 s[0..i-1] 包含的字符种类\n",
    "            pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 后缀 s[i+1..n-1] 包含的字符种类\n",
    "            suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        # 每种中间字符的回文子序列状态数组\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]\n",
    "        # 更新答案\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "        return res\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 前缀/后缀字符状态数组\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            # 前缀 s[0..i-1] 包含的字符种类\n",
    "            pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 后缀 s[i+1..n-1] 包含的字符种类\n",
    "            suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        # 每种中间字符的回文子序列状态数组\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]\n",
    "        # 更新答案\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 前缀/后缀字符状态数组\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            # 前缀 s[0..i-1] 包含的字符种类\n",
    "            pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 后缀 s[i+1..n-1] 包含的字符种类\n",
    "            suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "        # 每种中间字符的回文子序列状态数组\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]\n",
    "        # 更新答案\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0] * n\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] | 1 << (ord(s[i - 1]) - ord('a'))\n",
    "        suf = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            suf[i] = suf[i + 1] | 1 << (ord(s[i + 1]) - ord('a'))\n",
    "\n",
    "        overlaps = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            overlaps[ord(s[i]) - ord('a')] |= pre[i] & suf[i]\n",
    "        return sum(overlap.bit_count() for overlap in overlaps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*n\n",
    "        suf = [0]*n\n",
    "        for i, ch in enumerate(s):\n",
    "            if i==0:\n",
    "                pre[i] = 1<<(ord(ch)-ord('a'))\n",
    "            else:\n",
    "                pre[i] = pre[i-1] | (1<<(ord(ch)-ord('a')))\n",
    "        #print(pre)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i==n-1:\n",
    "                suf[i] = 1<<(ord(s[i])-ord('a'))\n",
    "            else:\n",
    "                suf[i] = suf[i+1] | (1<<(ord(s[i])-ord('a')))\n",
    "        #print(suf)\n",
    "        ans = [0]*26\n",
    "        for i in range(1, n-1):\n",
    "            tmp = pre[i-1] & suf[i+1]\n",
    "            ans[ord(s[i])-ord('a')] |= tmp\n",
    "        res = 0\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count('1')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 枚举两侧的字符\n",
    "    # O(n∣Σ∣+∣Σ∣^2) O(∣Σ∣)\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 枚举两侧字符\n",
    "        for i in range(26):\n",
    "            l, r = 0, n - 1\n",
    "            # 寻找该字符第一次出现的下标\n",
    "            while l < n and ord(s[l]) - ord('a') != i:\n",
    "                l += 1\n",
    "\n",
    "            # 寻找该字符最后一次出现的下标\n",
    "            while r >= 0 and ord(s[r]) - ord('a') != i:\n",
    "                r -= 1\n",
    "\n",
    "            if r - l < 2:\n",
    "                # 该字符未出现，或两下标中间的子串不存在\n",
    "                continue\n",
    "\n",
    "            # 利用哈希集合统计 s[l+1..r-1] 子串的字符总数，并更新答案\n",
    "            charset = set()\n",
    "            for k in range(l + 1, r):\n",
    "                charset.add(s[k])\n",
    "\n",
    "            res += len(charset)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    # 枚举中间的字符\n",
    "    # O(n+∣Σ∣) O(∣Σ∣)\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        # 前缀/后缀字符状态数组\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(n):\n",
    "            # 前缀 s[0..i-1] 包含的字符种类\n",
    "            pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 后缀 s[i+1..n-1] 包含的字符种类\n",
    "            suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))\n",
    "\n",
    "        # 每种中间字符的回文子序列状态数组\n",
    "        ans = [0] * 26\n",
    "        for i in range(1, n - 1):\n",
    "            ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]\n",
    "\n",
    "        # 更新答案\n",
    "        for i in range(26):\n",
    "            res += bin(ans[i]).count(\"1\")\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = set()\n",
    "        for j in range(26):\n",
    "            lst = [int(ord(w)-ord(\"a\")==j) for w in s]\n",
    "            pre = list(accumulate(lst, initial=0))\n",
    "            for i in range(1, n-1):\n",
    "                if pre[i] and pre[-1]-pre[i+1]:\n",
    "                    ans.add((s[i],j))\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    N =  pow(10, 5)\n",
    "\n",
    "    def __init__(self):\n",
    "        self.sum = [0] * (4*SegTree.N + 20)\n",
    "\n",
    "    def push_up(self, o):\n",
    "        self.sum[o] = self.sum[o << 1] | self.sum[o << 1 | 1]\n",
    "\n",
    "    def update1(self, o, pl, pr, i, x):\n",
    "        if pl == pr:\n",
    "            self.sum[o] |= x\n",
    "            return\n",
    "        mid = pl + pr >> 1\n",
    "\n",
    "        if i <= mid:\n",
    "            self.update1(o << 1, pl, mid, i, x)\n",
    "        if i > mid:\n",
    "            self.update1(o << 1 | 1, mid + 1, pr, i, x)\n",
    "        self.push_up(o)\n",
    "\n",
    "    def update(self, i, x):\n",
    "        self.update1(1, 0, SegTree.N, i, x)\n",
    "\n",
    "    def query1(self, o, pl, pr, l, r):\n",
    "        if r < pl or l > pr:\n",
    "            return 0\n",
    "        if pl >= l and pr <= r:\n",
    "            return self.sum[o]\n",
    "        ans = 0\n",
    "        mid = pl + pr >> 1\n",
    "        if l <= mid:\n",
    "            ans |= self.query1(o << 1, pl, mid, l, r)\n",
    "        if r > mid:\n",
    "            ans |= self.query1(o << 1 | 1, mid + 1, pr, l, r)\n",
    "        return ans\n",
    "\n",
    "    def query(self, l, r):\n",
    "        return self.query1(1, 0, SegTree.N, l, r)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromicSubsequence(self, s: str) -> int:\n",
    "        ##给定字符串s,返回长度为3，为回文串，且为s子序列的不同回文串个数\n",
    "        n = len(s)\n",
    "        a = [[0x3f3f3f3f, -1] * 26 for _ in range(26)]\n",
    "        ## follows the pattern A_A\n",
    "        ## use bit manipulation to simplify\n",
    "        seg = SegTree()\n",
    "\n",
    "        def cntone(x):\n",
    "            t = 0\n",
    "            while x > 0:\n",
    "                x -= x & (-x)\n",
    "                t += 1\n",
    "            return t\n",
    " \n",
    "\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            v = ord(c) - ord('a')\n",
    "            seg.update(i, 1<<v)\n",
    "            a[v][1] = max(a[v][1], i)\n",
    "            a[v][0] = min(a[v][0], i)\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            if a[i][0] != 0x3f3f3f3f and a[i][1] != -1 and a[i][1] > a[i][0] + 1:\n",
    "                ans += cntone(seg.query(a[i][0] + 1, a[i][1] - 1))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
